Exercici 14 (Tasca 2).
(regular languages,
minimization of DFAs,
pigeonhole principle,
hard exercise)
Almenys k ocurrències de cada símbol és un llenguatge regular
Donat k\in \mathbb N, considereu el llenguatge
L_k=\{w\in \{a,b,c\}^* \mid |w|_a\geq k \land |w|_b\geq k \land |w|_c\geq k\}\ .
Demostreu que per qualsevol k, L_k és un llenguatge regular.
Quants estats (en funció de k) té el mínim DFA que reconeix L_k?